// run: $exec < input
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
int n, m, test;
int map[1100][1100];
int sum[1100][1100];
int a[1000*1000+1000];
char s[1100];
int b[1100];
int bit[1100];
int sum2(int i) {
	int s = 0;
	while (i > 0) {
		s += bit[i];
		i -= i &-i;
	}
	return s;
}
void add(int i, int x) {
	while (i <= n) {
		bit[i] += x;
		i += i & -i;
	}
}
int main()
{

	// cout << (2 + 4 >> 1) << endl;
	scanf("%d", &test);
	while (test--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) {
				scanf("%s", &s);
			for (int j = 1; j <= n; j++) {
				map[i][j] = int(s[j-1] - '0');
			}
		}
		for (int i = 0; i <= n; i++) {
			sum[0][i] = sum[i][0] = 0;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j<= n; j++) {
				sum[i][j] = map[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
			}
		}
		int pos = 0;
		int t;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				int beg = 0, end = j+1, mid;
				t = beg;
				while (beg < end - 1) {
					mid = beg + end >> 1;
					if (sum[i][j] - sum[i-mid][j] - sum[i][j-mid] + sum[i-mid][j-mid] == mid * mid) {
						t = mid;
						beg = mid;
					}
					else end = mid;
				}
				a[pos++] = t;
			}
		}
		// for (int i = 0; i < pos; i++) cout << a[i] << ' '; cout << endl;
		memset(b, 0 ,sizeof(b));
		memset(bit, 0, sizeof(bit));
		for (int i = 0; i < pos; i++) {
			b[a[i]] ++;
		}
		for (int i = 1; i <= n; i++) {
			add(i, b[i]);
		}
		while (m--) {
			scanf("%d", &t);
			if (t == 1) printf("%d\n", sum2(n));
			else
				printf("%d\n", sum2(n) - sum2(t-1));
		}
	}
}
